package c_ch11.prim;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

import c_ch11.kruskal.Kruskal_try;
import c_ch11.kruskal.WeightedEdge_try;
import c_ch11.kruskal.WeightedGraph_try;

//时间应该是耗在add上，按照语意 每一条边都应该入队了一次，平均O(ElogE)，下边的出队最多也是O(ElogE)，整体还是O(ElogE)；
//不管采用Prim还是kruskal，都要考虑的是：1.图可能本身就不连通；2.顶点表示边会存储两次，使用边的语意时要避免重复访问；
public class Prim_try {
	
	private ArrayList<WeightedEdge_try> ret;
	private boolean[] visited;  //Prim的思路是从任意一个顶点出发，把所有顶点过一遍，已经pass的顶点作为切分的一组，然后选择最小的横切边；visited就起到涂色.分组的作用
	
	public Prim_try(String wg) {
		
		WeightedGraph_try g = new WeightedGraph_try(wg);
		
		ret = new ArrayList<>();
		visited = new boolean[g.getV()];
		Arrays.fill(visited, false);
		
		Queue<WeightedEdge_try> pq = new PriorityQueue<>();
		int curV = 0;
		for (int i = 0; i < g.getV()-1; i++) { 	//外层只是表示次数
			visited[curV] = true;
			Iterable<Integer> adj = g.adj(curV);
			for (Integer edge : adj) {
				if(!visited[edge])  //可作为横切边的才入队；   另一个角度看，这里也算是去重了，无向边用顶点表示会有重复表示的问题；
					pq.add(new WeightedEdge_try(curV, edge, g.weight(curV, edge)));  
			}
			
			boolean normal = false;
			while(!pq.isEmpty()) {
				WeightedEdge_try head = pq.poll();
				if(visited[head.getA()] != visited[head.getB()]) {  //随着顶点的访问，已经入队的原来可以作横切边的边可能会变的无法切分；
					ret.add(head);
					curV = head.getB();
					normal = true;
					break;
				}
			}
			
			//类似于Kruskal算法自己加的判断，并不影响算法整体时间复杂度； 暂时不觉得有什么问题； 如果用pq.isEmpty()来判断可能有问题，因为break的情况也有可能恰好是最后一个元素出队；
			if(!normal) {  //保证图是连通的； 如果图是连通的，在这个for循环里 一定每一轮都可以找到横切边，即正常返回break，如果while是因为迭代尽而出来，说明 不正常；
				ret.clear();  
				break;
			}
		}
//		System.out.println(pq);  //java里的排序默认都是从小到大，pq也不例外 是基于最小堆；
	}
	
	public Iterable<WeightedEdge_try> result() {
		ret.sort(null);  //仅为了方便对比结果，因为Prim的思路对于起点是不要求的，所以顺序比较随意；
		return ret;
	}
	
	public static void main(String[] args) {
		System.out.println(new Prim_try("wg.txt").result()); 
		System.out.println(new Prim_try("wg2.txt").result());   //这样下来，使用Prim算法就很方便 不用UF也不用CC而且pq还是内置的；
		
		System.out.println(new Kruskal_try("wg.txt").result());
		System.out.println(new Kruskal_try("wg2.txt").result());
	}
	
}
